﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <algorithm>

using namespace std;

//将它们「排序」之后，两个单词应该是「完全相同」的。
//所以，我们可以利⽤这个特性，将单词按照字典序排序，如果排序后的单词相同的话，就划分到同⼀
//组中。
//这时我们就要处理两个问题：
//• 排序后的单词与原单词需要能互相映射；
//• 将排序后相同的单词，「划分到同⼀组」；
class Solution
{
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs)
    {
        unordered_map<string, vector<string>> hash;
        // 1. 把所有的字⺟异位词分组
        for (auto& s : strs)
        {
            string tmp = s;
            sort(tmp.begin(), tmp.end());
            hash[tmp].push_back(s);
        }

        //// 2. 结果提取出来
        vector<vector<string>> ret;
        //for (auto& [x, y] : hash)
        //{
        //    ret.push_back(y);
        //}
        for (const auto& kv : hash) {
            const std::string& x = kv.first;
            const std::vector<std::string>& y = kv.second;
            ret.push_back(y);
        }
        return ret;
    }
};

//解决该问题需要我们快速定位到两个信息：
//• 两个相同的元素；
//• 这两个相同元素的下标。
//因此，我们可以使⽤「哈希表」，令数组内的元素做 key 值，该元素所对应的下标做 val 值，将
//「数组元素」和「下标」绑定在⼀起，存⼊到「哈希表」中。

//我们按照下标「从⼩到⼤」的顺序遍历数组，当遇到两个元素相同，并且⽐较它们的下标时，这两个
//下标⼀定是距离最近的，因为：
//• 如果当前判断符合条件直接返回 true ，⽆需继续往后查找。
//• 如果不符合条件，那么前⼀个下标⼀定不可能与后续相同元素的下标匹配（因为下标在逐渐变
//⼤），那么我们可以⼤胆舍去前⼀个存储的下标，转⽽将其换成新的下标，继续匹配。
class Solution
{
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k)
    {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); i++)
        {
            if (hash.count(nums[i]))
            {
                if (i - hash[nums[i]] <= k)
                    return true;
            }

            hash[nums[i]] = i;
        }

        return false;

    }
};

//出现「⾄少两次」的意思就是数组中存在着重复的元素，因此我们可以⽆需统计元素
//出现的数⽬。仅需在遍历数组的过程中，检查当前元素「是否在之前已经出现过」即可。
//因此我们可以利⽤哈希表，仅需存储数「组内的元素」。在遍历数组的时候，⼀边检查哈希表中是否
//已经出现过当前元素，⼀边将元素加⼊到 哈希表中。

class Solution
{
public:
    bool containsDuplicate(vector<int>& nums)
    {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); i++)
        {
            if (hash.count(nums[i]))
                return true;
            hash[nums[i]] = i;
        }

        return false;

    }
};

//给定两个由小写字母组成的字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。
class Solution
{
public:
    bool CheckPermutation(string s1, string s2)
    {
        if (s1.size() != s2.size())
            return false;
        int hash[26] = { 0 };
        for (auto ch : s1)
        {
            hash[ch - 'a']++;
        }

        for (auto ch : s2)
        {
            hash[ch - 'a']--;
        }

        for (int i = 0; i < 26; i++)
        {
            if (hash[i]) return false;
        }

        return true;
    }
};

//给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，
//并返回它们的数组下标。
//
//你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
//
//你可以按任意顺序返回答案。
class Solution
{
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); i++)
        {
            if (hash.count(target - nums[i]))
                return { i,hash[target - nums[i]] };
            hash[nums[i]] = i;
        }

        return {};

    }
};


//给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
//
//请你将两个数相加，并以相同形式返回一个表示和的链表。
//
//你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 struct ListNode {
     int val;
     ListNode *next;
     ListNode() : val(0), next(nullptr) {}
     ListNode(int x) : val(x), next(nullptr) {}
     ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution
{
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
    {
        ListNode* cur1 = l1, * cur2 = l2;
        ListNode* newhead = new ListNode(0);
        ListNode* tail = newhead;
        int t = 0;//保存进位
        while (cur1 || cur2 || t)
        {
            if (cur1)
            {
                t += cur1->val;
                cur1 = cur1->next;
            }

            if (cur2)
            {
                t += cur2->val;
                cur2 = cur2->next;
            }

            tail->next = new ListNode(t % 10);
            tail = tail->next;
            t /= 10;
        }

        ListNode* ret = newhead->next;
        delete newhead;

        return ret;
    }
};


//给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。
//你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
struct ListNode {
      int val;
      ListNode *next;
      ListNode() : val(0), next(nullptr) {}
      ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
 };

class Solution
{
public:
    ListNode* swapPairs(ListNode* head)
    {
        if (head == nullptr || head->next == nullptr) return head;
        ListNode* newhead = new ListNode(0);
        newhead->next = head;
        ListNode* prev = newhead, * cur = prev->next, * next = cur->next, * nnext = next->next;
        while (cur && next)
        {
            prev->next = next;
            next->next = cur;
            cur->next = nnext;

            prev = cur;
            cur = nnext;
            if (cur) next = cur->next;
            if (next) nnext = next->next;
        }

        ListNode* ret = newhead->next;
        delete newhead;

        return ret;

    }
};

//珠玑妙算游戏（the game of master mind）的玩法如下。
//
//计算机有4个槽，每个槽放一个球，颜色可能是红色（R）、
//黄色（Y）、绿色（G）或蓝色（B）。例如，计算机可能有RGGB 4种（槽1为红色，槽2、3为绿色，槽4为蓝色）。
//作为用户，你试图猜出颜色组合。打个比方，你可能会猜YRGB。要是猜对某个槽的颜色，则算一次“猜中”；
//要是只猜对颜色但槽位猜错了，则算一次“伪猜中”。注意，“猜中”不能算入“伪猜中”。
//
//给定一种颜色组合solution和一个猜测guess，编写一个方法，返回猜中和伪猜中的次数answer，
//其中answer[0]为猜中的次数，answer[1]为伪猜中的次数。
class Solution
{
public:
    vector<int> masterMind(string solution, string guess)
    {
        int right = 0;
        for (int i = 0; i < 4; i++)
        {
            if (solution[i] == guess[i])
            {
                right++;
            }
        }
        int hash[26] = { 0 };
        for (int i = 0; i < 4; i++)
        {
            hash[solution[i] - 'A']++;
        }

        int fright = 0;
        for (int i = 0; i < 4; i++)
        {
            if (hash[guess[i] - 'A'] > 0)
            {
                fright++;
                hash[guess[i] - 'A']--;
            }
        }

        return { right,fright - right };
    }
};

//给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。
//（注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> ret;
        unordered_map<int, int> hash;
        for (int i = 0; i < numbers.size(); i++)
        {
            int x = target - numbers[i];
            if (hash.count(x))
                return { hash[x] + 1,i + 1 };
            hash[numbers[i]] = i;
        }

        return {};
    }
};

//给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。
//1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
//2.假设 nums[-1] = nums[n] =−∞−∞
//3.对于所有有效的 i 都有 nums[i] != nums[i + 1]
//4.你可以使用O(logN)的时间复杂度实现此问题吗？

class Solution {
public:
    
    int findPeakElement(vector<int>& nums)
    {
        if (nums.size() == 1) return 0;
        if (nums.size() == 2)
        {
            if (nums[0] > nums[1])
                return 0;
            else
                return 1;
        }
        int i = 1;
        for (; i < nums.size() - 1; i++)
        {
            if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1])
                return i;
        }
        if (i == nums.size() - 1)
        {
            if (nums[0] > nums[nums.size() - 1])
                return 0;
            else
                return nums.size() - 1;
        }

        return -1;

    }
};


// 在一个长为 字符串中找到第一个只出现一次的字符, 并返回它的位置, 如果没有则返回 - 1（需要区分大小写）.（从0开始计数）

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        int hash[128] = { 0 };
        for (auto ch : str)
        {
            hash[ch]++;
        }
        for (int i = 0; i < str.size(); i++)
        {
            if (hash[str[i]] == 1)
                return i;
        }

        return -1;
    }
};
int main()
{
	return 0;
}